package leetcode.hot100;

import leetcode.common.TreeNode;

import java.util.ArrayList;

@SuppressWarnings("all")
public class _98_验证二叉搜索树_两次遍历 {

    // 先获取中序遍历的结果序列
    // 再判断该序列是否按照严格升序排列
    // 注意：这个题目说明的二叉树搜索树必须要求严格递增，两个结点的值相同都不是二叉搜索树

    private ArrayList<Integer> inorderList;

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        inorderList = new ArrayList<>();
        inorder(root);
        int len = inorderList.size();
        for (int i = 1; i < len; i++) {
            if (inorderList.get(i - 1) >= inorderList.get(i)) return false;
        }
        return true;
    }

    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        inorderList.add(root.val);
        inorder(root.right);
    }
}
